package com.zhugang.week13.sorting;

/**
 * @program algorithms
 * @description: insertionSort
 * @author: chanzhugang
 * @create: 2022/09/30 21:54
 */
public class InsertionSort implements IMutableSorter {

    /**
     * 插入排序(类似抓扑克牌)：将未排序的值插入到正确的位置
     * O(n^2)
     *
     * @param A
     */
    @Override
    public void sort(int[] A) {
        for (int i = 1; i < A.length; i++) {
            // 抓到的牌
            int val = A[i];
            int j = i;
            while (j > 0 && A[j - 1] > val) {
                // 前一张牌比抓到的牌大，后移一位且j向前移动一位
                A[j] = A[j - 1];
                j--;
            }
            // 将抓到的牌插入正确位置
            A[j] = val;
        }
    }
}